package cn.doourbest.learnspring.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @author: zhangsc
 * @create: 2019/12/26
 */
public class Solution2 {
    private static int maxLength = 0;

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int maxLength = 0;
        ListNode listNode = null;
        ListNode tt = null;
        ListNode upT = null;

        ListNode tt1 = l1;
        ListNode tt2 = l2;
        int num = 0;
        while ((tt1 != null) || ( tt2 != null)){

            Integer ii1 = 0;
            Integer ii2 = 0;

            if(tt1 != null){
                ii1 = tt1.val;
                tt1 = tt1.next;
            }
            if(tt2 != null){
                ii2 = tt2.val;
                tt2 = tt2.next;
            }

            if(maxLength == 1){
                ii1 += 1;
            }
            int si = 0;
            if(ii1 + ii2 >= 10){
                maxLength = 1;
                si = ii1 + ii2 - 10;
            }else{
                maxLength = 0;
                si = ii1 + ii2;
            }
            if(num == 0){
                listNode = new ListNode(si);
                upT = listNode;
                num ++;
            }else{
                tt = new ListNode(si);
                upT.next = tt;
                upT = tt;
            }

        }
        if(maxLength == 1){
            tt = new ListNode(1);
            upT.next = tt;
        }

        return listNode;
        /****
         *          int[] ii = {2,4,3};
         *         int[] jj = {5,6,4};
         *
         *         ListNode l1 = new ListNode(ii[0]);
         *         ListNode l2 = new ListNode(jj[0]);
         *
         *         ListNode tt = null;
         *         ListNode upTt = l1;
         *         for(int f = 1;f<ii.length;f++){
         *             tt = new ListNode(ii[f]);
         *             upTt.next = tt;
         *             upTt = tt;
         *         }
         *
         *         upTt = l2;
         *         for(int f = 1;f<jj.length;f++){
         *             tt = new ListNode(jj[f]);
         *             upTt.next = tt;
         *             upTt = tt;
         *         }
         *         System.out.println(l1);
         *         System.out.println(l2);
         *
         *         System.out.println(new Solution2().addTwoNumbers(l1,l2));
        */
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double a = 0;
        int len1 = nums1.length;
        int len2 = nums2.length;
        int maxlen = len1 + len2;

        int num = 0;
        int len = len1;
        if(len < len2){
            len = len2;
        }

        int middle = 0;
        if(maxlen % 2 == 0){
            middle = maxlen / 2;
        }else{
            middle = (maxlen + 1) / 2;
        }

        int now1 = 0;
        int now2 = 0;

        int middlenum1 = 0;
        int middlenum2 = 0;
        while(true){
            int curr = 0;
            if(len1 > now1 && len2 > now2){
                if(nums1[now1] > nums2[now2]){
                    num ++;
                    curr = nums2[now2];
                    now2++;
                }else{
                    curr = nums1[now1];
                    num ++;
                    now1 ++;
                }
                if(num == middle){
                    middlenum1 = curr;
                }else if(num == middle + 1){
                    middlenum2 = curr;
                    break;
                }
            }
            else if(len2 > now2){
                curr = nums2[now2];
                num++;
                now2 ++;
                if(num == middle){
                    middlenum1 = curr;
                }else if(num == middle + 1){
                    middlenum2 = curr;
                    break;
                }
            }else if(len1 > now1){
                curr = nums1[now1];
                num++;
                now1 ++;
                if(num == middle){
                    middlenum1 = curr;
                }else if(num == middle + 1){
                    middlenum2 = curr;
                    break;
                }
            }else{
                break;
            }

        }

        if(maxlen % 2 == 0){
            return (new Double(middlenum1) + new Double(middlenum2)) / new Double(2);
        }else{
            return new Double(middlenum1);
        }

        /**8 int[] i1 = {1,3,4,5};
         int[] i2 = {2};
         System.out.println(new Solution2().findMedianSortedArrays(i1,i2));*/
    }

    public String longestPalindrome(String s) {
        if(s.length() == 0){
            return "";
        }
        int ll = s.length();

        for (int j = ll; j > 0; j--) {
            for (int i = 0; i < ll; i++) {
                if (i + j > ll) {
                    break;
                }
                if (checkString(s.substring(i, i + j))) {
                    return s.substring(i, i + j);
                }
            }
        }
        return s.substring(0,1);
       // System.out.println(new Solution2().longestPalindrome("asdfasdfasdfasdfdasafa"));
    }

    public boolean checkString(String s){

        for( int j = 0,k= s.length() - 1; j<=k ; j++,k-- ){
            if(s.charAt(j) != s.charAt(k)){
                return false;
            }
        }
        return true;
    }

    public int[] twoSum(int[] nums, int target) {
        int[] re = new int[2];
        for( int i = 0; i < nums.length; i++) {
            int ret = target - nums[i];
            for(int kk = 0; kk < nums.length; kk++){
                if(nums[kk] == ret && kk != i){
                    re[0] = i;
                    re[1] = kk;
                    return re;
                }
            }
        }
        return re;
        //        int[] ints = new Solution2().twoSum(aa, target);
    }

    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0){
            return 0;
        }
        if(s.length() == 1){
            return 1;
        }

        int maxret = 0;
        int start = 0;
        int max = s.length();
        int nextStart = 1;
        for(int k =0; k < s.length(); k++){
            if(k == max){
                if (s.substring(start, k).length() > maxret) {
                    maxret = s.substring(start, k).length();
                }
                max = s.length();
                k = nextStart;
                start = k;
                nextStart = start + 1;
                k--;
                continue;
            }

            int i = s.indexOf(s.charAt(k), k + 1);
            if(i > -1){
                if (i < max) {
                    if(max != s.length()){
                        nextStart ++;
                    }
                    max = i;
                }
            }
        }

        if (s.substring(start).length() > maxret) {
            maxret = s.substring(start).length();
        }
        return maxret;
     //   System.out.println(solution2.lengthOfLongestSubstring("abcabcbb"));
    }


    public String convert(String s, int numRows) {
        int length = s.length();

        Map<Integer , ListNodeZ> map = new HashMap<>();

        boolean up = true;
        Integer a = 0;
        for( int x = 0; x < length; x ++){
            if(map.get(a) == null) {
                ListNodeZ listNode = new ListNodeZ();
                listNode.var = s.charAt(x);
                listNode.current = listNode;
                map.put(a,listNode);
            }else{
                ListNodeZ listNodeZ = map.get(a);
                listNodeZ.addNext(s.charAt(x));
            }
            if(up){
                a ++;
                if(a == numRows){
                    a = a - 2;
                    if(a < 0){
                        a = 0;
                    }
                    up = false;
                }
            }else{
                a--;
                if(a == -1){
                    a = a + 2;
                    if(a >= numRows){
                        a = 0;
                    }
                    up = true;
                }
            }
        }

        StringBuilder stringBuilder = new StringBuilder();
        for( Integer integer = 0 ; integer < numRows ;integer ++){
            ListNodeZ listNodeZ = map.get(integer);
            while(listNodeZ != null){
                stringBuilder.append(listNodeZ.var);
                listNodeZ = listNodeZ.next;
            }
        }

        return stringBuilder.toString();
    }
    public class ListNodeZ{
        public char var;
        public ListNodeZ next;
        public ListNodeZ current;


        public void addNext(char c){
            ListNodeZ listNode = new ListNodeZ();
            listNode.var = c;
            current.next = listNode;
            current = listNode;
        }
        //System.out.println(solution2.convert("ABC",1));
    }


    public int reverse(int x) {
        String s = String.valueOf(x);

        boolean zhengshu = true;

        int i = 0;
        if(x < 0){
            i = 1;
            zhengshu = false;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for(  ; i< s.length(); i ++){
            stringBuilder.append(s.charAt(i));
        }


        String s1 = stringBuilder.reverse().toString();
        if(zhengshu){
            if(isMoreThanMax(s1)){
                return 0;
            }
        }else{
            if(isLessMin("-" + s1)){
                return 0;
            }
        }



        if(zhengshu){
            return Integer.valueOf(s1);
        }else{
            return Integer.valueOf("-" + s1);
        }

    }

    public boolean isMoreThanMax(String s){
        String b = "2147483647";
        if(s.length() < 10){
            return false;
        }
        for( int i =0; i < 10;i++){
            if(s.charAt(i) < b.charAt(i)){
                return false;
            }else if (s.charAt(i) == b.charAt(i)){
            }else{
                return true;
            }
        }
        return false;

    }

    public boolean isLessMin(String s){
        String b = "-2147483648";
        if(s.length() < 11){
            return false;
        }

        for( int i =0; i < 11;i++){
            if(s.charAt(i) < b.charAt(i)){
                return false;
            }else if (s.charAt(i) == b.charAt(i)){
            }else{
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();



    //        System.out.println(solution2.lengthOfLongestSubstring("s"));

    }




    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        @Override
        public String toString() {
            return "{" +val + next + '}';
        }
    }
}
